#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization;
using System.Security.Permissions;
using AbstractClass.Linq;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a node associated with an element in the <see cref="Tree&lt;T&gt;"/>.
    /// </summary>
    /// <typeparam name="T">The type of the data associated with the node.</typeparam>
    [Serializable]
    public class TreeNode<T> : AbstractNode<T>
    {
        /// <summary>
        /// An internal list of all tree nodes in the tree.
        /// </summary>
        protected readonly List<TreeNode<T>> ChildNodes;

        /// <summary>
        /// Initializes a new instance of the <see cref="TreeNode&lt;T&gt;"/> class.
        /// </summary>
        public TreeNode()
        {
            ChildNodes = new List<TreeNode<T>>();
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="TreeNode&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="value">The value associated with the node.</param>
        public TreeNode(T value)
            : base(value)
        {
            ChildNodes = new List<TreeNode<T>>();
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="TreeNode&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="value">The value associated with node.</param>
        /// <param name="children">The child nodes associated with the new <see cref="TreeNode&lt;T&gt;"/>.</param>
        public TreeNode(T value, List<TreeNode<T>> children)
            : base(value)
        {
            ChildNodes = children;
            foreach (var treeNode in children)
            {
                treeNode.Depth = Depth + 1;
                treeNode.Parent = this;
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="TreeNode&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="data">The data associated with node.</param>
        /// <param name="children">The data associated with the immediate child nodes.</param>
        public TreeNode(T data, params T[] children)
            : base(data)
        {
            ChildNodes = children.Select(node => new TreeNode<T>(node)).ToList();
            foreach (var treeNode in ChildNodes)
            {
                treeNode.Depth = Depth + 1;
                treeNode.Parent = this;
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="TreeNode&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="data">The data associated with node.</param>
        /// <param name="children">Immediate child nodes of the new <see cref="TreeNode&lt;T&gt;"/>.</param>
        public TreeNode(T data, params TreeNode<T>[] children)
            : this(data, children.ToList())
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="TreeNode&lt;T&gt;"/> class.
        /// </summary>
        /// <param name = "info">The <see cref = "T:System.Runtime.Serialization.SerializationInfo" /> to populate with data. 
        /// </param>
        /// <param name = "context">The destination (see <see cref = "T:System.Runtime.Serialization.StreamingContext" />) for this serialization. 
        /// </param>
        protected TreeNode(SerializationInfo info, StreamingContext context)
            : base(info, context)
        {
            Value = info.GetValue("Value", typeof (T)) is T ? (T) info.GetValue("Value", typeof (T)) : default(T);
            ChildNodes = info.GetValue("ChildNodes", typeof (List<TreeNode<T>>)) as List<TreeNode<T>>;
            Parent = info.GetValue("Parent", typeof (TreeNode<T>)) as TreeNode<T>;
            Depth = (int) info.GetValue("Depth", typeof (int));
        }

        /// <summary>
        /// Gets the child node associated with this instance.
        /// </summary>
        /// <value>The child node associated with this instance.</value>
        public List<TreeNode<T>> Children
        {
            get { return ChildNodes; }
        }

        #region Overrides of AbstractNode<T>

        /// <summary>
        /// Gets a value indicating whether this instance is a leaf node.
        /// </summary>
        /// <value><c>true</c> if this instance is leaf node; otherwise, <c>false</c>.</value>
        public override bool IsLeaf
        {
            get { return ChildNodes.IsNullOrEmpty(); }
        }

        /// <summary>
        /// Gets the child node count of the node.
        /// </summary>
        /// <value>The child node count.</value>
        public override int ChildCount
        {
            get { return ChildNodes.Count; }
        }

        /// <summary>
        /// Determines whether the current instance is equal to <paramref name="other"/> or not.
        /// </summary>
        /// <param name="other">The other node.</param>
        /// <returns>
        /// <c>true</c> if this instance is equal to <paramref name="other" />; otherwise, <c>false</c>.
        /// </returns>
        public override bool Equals(AbstractNode<T> other)
        {
            if (other == null) return false;
            if (!(other is TreeNode<T>)) return false;
            if (ReferenceEquals(this, other)) return true;
            var otherNode = other as TreeNode<T>;

            if (Value.Equals(otherNode.Value))
            {
                if (ChildCount != otherNode.ChildCount)
                    return false;
                for (int i = 0; i < ChildCount; i++)
                {
                    if (!ChildNodes[i].Equals(otherNode.ChildNodes[i]))
                        return false;
                }
                return !Children.Any(treeNode => !treeNode.Equals(other));
            }
            return false;
        }

        /// <summary>
        ///   Populates a <see cref = "T:System.Runtime.Serialization.SerializationInfo" /> with the data needed to serialize the target object.
        /// </summary>
        /// <param name = "info">The <see cref = "T:System.Runtime.Serialization.SerializationInfo" /> to populate with data. 
        /// </param>
        /// <param name = "context">The destination (see <see cref = "T:System.Runtime.Serialization.StreamingContext" />) for this serialization. 
        /// </param>
        /// <exception cref = "T:System.Security.SecurityException">The caller does not have the required permission. 
        /// </exception>
        [SecurityPermission(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
        public override void GetObjectData(SerializationInfo info, StreamingContext context)
        {
            info.SetType(typeof (TreeNode<T>));
            info.AddValue("Value", Value);
            info.AddValue("ChildNodes", ChildNodes);
            info.AddValue("Parent", Parent);
            info.AddValue("Depth", Depth);
        }

        #endregion

        /// <summary>
        /// Deletes this instance by deleting all descendant nodes.
        /// </summary>
        public void Delete()
        {
            foreach (var child in ChildNodes)
            {
                child.Delete();
            }
            ChildNodes.Clear();
            Value = default(T);
        }

        /// <summary>
        ///   Determines whether the specified node is sibling of this node.
        /// </summary>
        /// <param name = "node">The node to check for sibling relation.</param>
        /// <returns>
        ///   <c>true</c> if the specified node is sibling; otherwise, <c>false</c>.
        /// </returns>
        /// <remarks>
        /// </remarks>
        public bool IsSibling(TreeNode<T> node)
        {
            return Parent != null && ((TreeNode<T>) Parent).ChildNodes.Contains(node);
        }

        /// <summary>
        /// Determines whether any descendant nodes of this instance contain the <paramref name="data"/>.
        /// </summary>
        /// <param name="data">The data to search in the descendant nodes.</param>
        /// <returns><see cref="TreeNode&lt;T&gt;"/> if the specified value is found; otherwise, <c>null</c>.
        /// </returns>
        public virtual TreeNode<T> HasDescendant(T data)
        {
            return ToEnumerable(TraversalOrder.DepthFirst).FirstOrDefault(node => node.Value.Equals(data));
        }

        /// <summary>
        /// Determines whether any descendant nodes of this instance contain the <paramref name="node"/>.
        /// </summary>
        /// <param name="node">The node to search in the descendant nodes.</param>
        /// <returns>
        /// <c>true</c> if the specified node has child; otherwise, <c>false</c>.
        /// </returns>
        public virtual bool HasDescendant(TreeNode<T> node)
        {
            return ToEnumerable(TraversalOrder.DepthFirst).Contains(node);
        }

        /// <summary>
        /// Gets all the descendant nodes in a order specified by <see cref="TraversalOrder"/>.
        /// </summary>
        /// <param name="traversalOrder">Order of the tree traversal.</param>
        /// <returns>All descendant nodes of this instance.</returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="traversalOrder"/> is null.</exception>
        public virtual IEnumerable<TreeNode<T>> ToEnumerable(TraversalOrder traversalOrder)
        {
            switch (traversalOrder)
            {
                case TraversalOrder.DepthFirst:
                    return ToDepthFirstEnumerable();
                case TraversalOrder.BreadthFirst:
                    return ToBreadthFirstEnumerable();
                default:
                    throw new ArgumentOutOfRangeException("traversalOrder");
            }
        }

        /// <summary>
        /// Fetches all the descendant nodes in Depth-First fashion.
        /// </summary>
        /// <returns>
        /// A collection of nodes ordered in depth-first fashion.
        /// </returns>
        protected IEnumerable<TreeNode<T>> ToDepthFirstEnumerable()
        {
            yield return this;

            foreach (var e in ChildNodes.Select(child => child.ToDepthFirstEnumerable().GetEnumerator()))
            {
                while (e.MoveNext())
                {
                    yield return e.Current;
                }
            }
        }

        /// <summary>
        /// Fetches all the descendant nodes in Breadth-First fashion.
        /// </summary>
        /// <returns>
        /// A collection of nodes ordered in breadth-first fashion.
        /// </returns>
        protected IEnumerable<TreeNode<T>> ToBreadthFirstEnumerable()
        {
            var queue = new Queue<TreeNode<T>>();
            queue.Enqueue(this);

            while (0 < queue.Count)
            {
                TreeNode<T> node = queue.Dequeue();
                if (node == null) continue;
                foreach (var child in node.ChildNodes)
                {
                    queue.Enqueue(child);
                }
                yield return node;
            }
        }

        /// <summary>
        /// Adds the <paramref name="value"/> as a child of this instance.
        /// </summary>
        /// <param name="value">The data to add as child of this instance.</param>
        public void AddChild(T value)
        {
            var node = new TreeNode<T>(value);
            AddChild(node);
        }

        /// <summary>
        /// Adds the <paramref name="node"/> as a child node of this instance.
        /// </summary>
        /// <param name="node">The child node to add.</param>
        public void AddChild(TreeNode<T> node)
        {
            node.Parent = this;
            ChildNodes.Add(node);
            node.Depth = Depth + 1;
        }

        /// <summary>
        /// Adds a collection of data as the children of this instance.
        /// </summary>
        /// <param name="values">The collection of data to add.</param>
        public void AddChildren(IEnumerable<T> values)
        {
            foreach (T treeNode in values)
            {
                AddChild(treeNode);
            }
        }

        /// <summary>
        /// Adds a collection of <see cref="TreeNode&lt;T&gt;"/> as the children of this instance.
        /// </summary>
        /// <param name="nodes">The collection of nodes to add as children.</param>
        public void AddChildren(IEnumerable<TreeNode<T>> nodes)
        {
            foreach (var treeNode in nodes)
            {
                AddChild(treeNode);
            }
        }

        /// <summary>
        /// Removes the child element from the children of this instance.
        /// </summary>
        /// <param name="value">The value to remove from the children.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool RemoveChild(T value)
        {
            TreeNode<T> node = HasDescendant(value);
            return node != null && ChildNodes.Remove(node);
        }

        /// <summary>
        /// Removes the child node from the children of this instance.
        /// </summary>
        /// <param name="node">The node to remove from the children.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool RemoveChild(TreeNode<T> node)
        {
            return ChildNodes.Remove(node);
        }

        /// <summary>
        /// Removes all child nodes from this instance.
        /// </summary>
        public void ClearChildren()
        {
            ChildNodes.Clear();
        }
    }
}